package main.剑指OfferⅠ;

import java.util.*;

public class Day15 {
    public static void main(String[] args) {
        System.out.println("剑指Offer34.二叉树中和为某个值的路径");
        System.out.println("剑指Offer36.二叉搜索树与双向链表");
        System.out.println("剑指Offer54.二叉搜索树的第K大节点");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
       this.val = val;
       this.left = left;
        this.right = right;
    }
}

class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

class Offer34{
    List<List<Integer>> list;
    public void  process(List<Integer> prePath,int curTarget,TreeNode curNode){
        List<Integer> curList=new ArrayList<>(prePath);
        curList.add(curNode.val);
        if (curNode.left==null&&curNode.right==null&&curTarget==curNode.val){//满足路径添加
            list.add(curList);
            return;
        }
        if (curNode.left!=null) process(curList,curTarget-curNode.val,curNode.left);//左子树
        if (curNode.right!=null) process(curList,curTarget-curNode.val,curNode.right);//右子树
    }
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        list=new ArrayList<>();
        List<Integer> curList=new ArrayList<>();
        if (root!=null) process(curList,target,root);
        return list;
    }
}

class Offer36{
    public Node treeToDoublyList(Node root) {//需改进
        List<Node> nodeList=new ArrayList<>();
        if (root!=null) {
            Stack<Node> stack=new Stack<>();
            stack.add(root);
            while (!stack.isEmpty()){//获取所有节点
                root=stack.pop();
                nodeList.add(root);
                if (root.left!=null) stack.add(root.left);
                if (root.right!=null) stack.add(root.right);
            }
            Collections.sort(nodeList, new Comparator<Node>() {//排序
                @Override
                public int compare(Node o1, Node o2) {
                    return o1.val - o2.val;
                }
            });
            int size=nodeList.size();
            for (int i=0;i<size;i++){//左指前，右指后
                Node curNode=nodeList.get(i),lastNode=null,nextNode=nodeList.get((i+1)%size);
                if (i==0) lastNode=nodeList.get(size-1);
                else if (i==size-1) lastNode=nodeList.get(i-1);
                else lastNode=nodeList.get(i-1);
                curNode.left=lastNode;
                curNode.right=nextNode;
            }
            return nodeList.get(0);
        }
        return null;
    }
}

class Offer54{
    public int kthLargest(TreeNode root, int k) {//需改进
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()){
            root=stack.pop();
            list.add(root.val);
            if (root.left!=null) stack.add(root.left);
            if (root.right!=null) stack.add(root.right);
        }
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        return list.get(k-1);
    }
}